home *** CD-ROM | disk | FTP | other *** search
/ Developer CD Series 1995 August: Tool Chest / Dev.CD Aug 95 TC / Dev.CD Aug 95 TC.toast / Tool Chest / Development Tools & Languages / Dylan Related / Marlais / Marlais 0.5.9-portable sources / gc / blacklst.c < prev    next >
Encoding:
C/C++ Source or Header  |  1995-03-15  |  6.1 KB  |  196 lines  |  [TEXT/ttxt]
  1. /* 
  2.  * Copyright 1988, 1989 Hans-J. Boehm, Alan J. Demers
  3.  * Copyright (c) 1991-1994 by Xerox Corporation.  All rights reserved.
  4.  *
  5.  * THIS MATERIAL IS PROVIDED AS IS, WITH ABSOLUTELY NO WARRANTY EXPRESSED
  6.  * OR IMPLIED.  ANY USE IS AT YOUR OWN RISK.
  7.  *
  8.  * Permission is hereby granted to use or copy this program
  9.  * for any purpose,  provided the above notices are retained on all copies.
  10.  * Permission to modify the code and to distribute modified code is granted,
  11.  * provided the above notices are retained, and a notice that the code was
  12.  * modified is included with the above copyright notice.
  13.  */
  14. /* Boehm, May 19, 1994 1:56 pm PDT */
  15. # include "gc_priv.h"
  16.  
  17. /*
  18.  * We maintain several hash tables of hblks that have had false hits.
  19.  * Each contains one bit per hash bucket;  If any page in the bucket
  20.  * has had a false hit, we assume that all of them have.
  21.  * See the definition of page_hash_table in gc_private.h.
  22.  * False hits from the stack(s) are much more dangerous than false hits
  23.  * from elsewhere, since the former can pin a large object that spans the
  24.  * block, eventhough it does not start on the dangerous block.
  25.  */
  26.  
  27. /*
  28.  * Externally callable routines are:
  29.  
  30.  * GC_add_to_black_list_normal
  31.  * GC_add_to_black_list_stack
  32.  * GC_promote_black_lists
  33.  * GC_is_black_listed
  34.  *
  35.  * All require that the allocator lock is held.
  36.  */
  37.  
  38. /* Pointers to individual tables.  We replace one table by another by     */
  39. /* switching these pointers.                         */
  40. word * GC_old_normal_bl;
  41.         /* Nonstack false references seen at last full        */
  42.         /* collection.                        */
  43. word * GC_incomplete_normal_bl;
  44.         /* Nonstack false references seen since last        */
  45.         /* full collection.                    */
  46. word * GC_old_stack_bl;
  47. word * GC_incomplete_stack_bl;
  48.  
  49. void GC_clear_bl();
  50.  
  51. void GC_bl_init()
  52. {
  53. # ifndef ALL_INTERIOR_POINTERS
  54.     GC_old_normal_bl = (word *)
  55.                  GC_scratch_alloc((word)(sizeof (page_hash_table)));
  56.     GC_incomplete_normal_bl = (word *)GC_scratch_alloc
  57.                         ((word)(sizeof(page_hash_table)));
  58.     if (GC_old_normal_bl == 0 || GC_incomplete_normal_bl == 0) {
  59.         GC_err_printf0("Insufficient memory for black list\n");
  60.         EXIT();
  61.     }
  62.     GC_clear_bl(GC_old_normal_bl);
  63.     GC_clear_bl(GC_incomplete_normal_bl);
  64. # endif
  65.     GC_old_stack_bl = (word *)GC_scratch_alloc((word)(sizeof(page_hash_table)));
  66.     GC_incomplete_stack_bl = (word *)GC_scratch_alloc
  67.                         ((word)(sizeof(page_hash_table)));
  68.     if (GC_old_stack_bl == 0 || GC_incomplete_stack_bl == 0) {
  69.         GC_err_printf0("Insufficient memory for black list\n");
  70.         EXIT();
  71.     }
  72.     GC_clear_bl(GC_old_stack_bl);
  73.     GC_clear_bl(GC_incomplete_stack_bl);
  74. }
  75.         
  76. void GC_clear_bl(doomed)
  77. word *doomed;
  78. {
  79.     BZERO(doomed, sizeof(page_hash_table));
  80. }
  81.  
  82. void GC_copy_bl(old, new)
  83. word *new, *old;
  84. {
  85.     BCOPY(old, new, sizeof(page_hash_table));
  86. }
  87.  
  88. /* Signal the completion of a collection.  Turn the incomplete black    */
  89. /* lists into new black lists, etc.                    */             
  90. void GC_promote_black_lists()
  91. {
  92.     word * very_old_normal_bl = GC_old_normal_bl;
  93.     word * very_old_stack_bl = GC_old_stack_bl;
  94.     
  95.     GC_old_normal_bl = GC_incomplete_normal_bl;
  96.     GC_old_stack_bl = GC_incomplete_stack_bl;
  97. #   ifndef ALL_INTERIOR_POINTERS
  98.       GC_clear_bl(very_old_normal_bl);
  99. #   endif
  100.     GC_clear_bl(very_old_stack_bl);
  101.     GC_incomplete_normal_bl = very_old_normal_bl;
  102.     GC_incomplete_stack_bl = very_old_stack_bl;
  103. }
  104.  
  105. void GC_unpromote_black_lists()
  106. {
  107. #   ifndef ALL_INTERIOR_POINTERS
  108.       GC_copy_bl(GC_old_normal_bl, GC_incomplete_normal_bl);
  109. #   endif
  110.     GC_copy_bl(GC_old_stack_bl, GC_incomplete_stack_bl);
  111. }
  112.  
  113. # ifndef ALL_INTERIOR_POINTERS
  114. /* P is not a valid pointer reference, but it falls inside    */
  115. /* the plausible heap bounds.                    */
  116. /* Add it to the normal incomplete black list if appropriate.    */
  117. void GC_add_to_black_list_normal(p)
  118. word p;
  119. {
  120.     if (!(GC_modws_valid_offsets[p & (sizeof(word)-1)])) return;
  121.     {
  122.         register int index = PHT_HASH(p);
  123.         
  124.         if (HDR(p) == 0 || get_pht_entry_from_index(GC_old_normal_bl, index)) {
  125. #           ifdef PRINTBLACKLIST
  126.         if (!get_pht_entry_from_index(GC_incomplete_normal_bl, index)) {
  127.               GC_printf1("Black listing (normal) 0x%lx\n",
  128.                        (unsigned long) p);
  129.             }
  130. #           endif
  131.             set_pht_entry_from_index(GC_incomplete_normal_bl, index);
  132.         } /* else this is probably just an interior pointer to an allocated */
  133.           /* object, and isn't worth black listing.                */
  134.     }
  135. }
  136. # endif
  137.  
  138. /* And the same for false pointers from the stack. */
  139. void GC_add_to_black_list_stack(p)
  140. word p;
  141. {
  142.     register int index = PHT_HASH(p);
  143.         
  144.     if (HDR(p) == 0 || get_pht_entry_from_index(GC_old_stack_bl, index)) {
  145. #       ifdef PRINTBLACKLIST
  146.         if (!get_pht_entry_from_index(GC_incomplete_stack_bl, index)) {
  147.               GC_printf1("Black listing (stack) 0x%lx\n",
  148.                          (unsigned long)p);
  149.         }
  150. #       endif
  151.     set_pht_entry_from_index(GC_incomplete_stack_bl, index);
  152.     }
  153. }
  154.  
  155. /*
  156.  * Is the block starting at h of size len bytes black listed?   If so,
  157.  * return the address of the next plausible r such that (r, len) might not
  158.  * be black listed.  (R may not actually be in the heap.  We guarantee only
  159.  * that every smaller value of r after h is also black listed.)
  160.  * If (h,len) is not black listed, return 0.
  161.  * Knows about the structure of the black list hash tables.
  162.  */
  163. struct hblk * GC_is_black_listed(h, len)
  164. struct hblk * h;
  165. word len;
  166. {
  167.     register int index = PHT_HASH((word)h);
  168.     register word i;
  169.     word nblocks = divHBLKSZ(len);
  170.  
  171. #   ifndef ALL_INTERIOR_POINTERS
  172.       if (get_pht_entry_from_index(GC_old_normal_bl, index)
  173.           || get_pht_entry_from_index(GC_incomplete_normal_bl, index)) {
  174.         return(h+1);
  175.       }
  176. #   endif
  177.     
  178.     for (i = 0; ; ) {
  179.         if (GC_old_stack_bl[divWORDSZ(index)] == 0
  180.             && GC_incomplete_stack_bl[divWORDSZ(index)] == 0) {
  181.             /* An easy case */
  182.             i += WORDSZ - modWORDSZ(index);
  183.         } else {
  184.           if (get_pht_entry_from_index(GC_old_stack_bl, index)
  185.               || get_pht_entry_from_index(GC_incomplete_stack_bl, index)) {
  186.             return(h+i+1);
  187.           }
  188.           i++;
  189.         }
  190.         if (i >= nblocks) break;
  191.         index = PHT_HASH((word)(h+i));
  192.     }
  193.     return(0);
  194. }
  195.  
  196.